package Solution.problem053;

/**
 * @program Leetcode
 * @description: https://blog.csdn.net/lw_power/article/details/80892362
 * @author: lishangsheng
 * @create: 2019/04/02 18:13
 */
public class Solution {
    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(dp[i], res);
        }
        return res;
    }

    public static void main(String[] args){
        int[] test=new int[]{-2,1,-3,4,-1,2,1,-5,4};
        int result=maxSubArray(test);
        System.out.println(result);
    }

}
